package SortAlgorithm;

import static SortAlgorithm.SelectSort.swap;

public class HeapSort {
    public static void heapSort(int[] array){
        creatHeap(array);
        int end=array.length-1;
        while(end>=0){
            swap(array,0,end);
            shiftDown(array,0,end);
            end--;
        }
    }
    public static void shiftDown(int[] array,int parent,int len){
    int child=2*parent+1;
    while(child<len){
        if(child+1<len&&array[child]<array[child+1]){
             child++;
        }
        if(array[child]>array[parent]){
            swap(array,child,parent);
            parent=child;
            child=parent*2+1;
        }else{
            break;
        }
    }
    }

    public static void creatHeap(int[] array){
        for(int i=(array.length-2)/2;i>=0;i--){
                shiftDown(array,i,array.length);
    }
}
}
